package medium;//以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间，并返
//回一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间。
//
//
//
// 示例 1：
//
//
//输入：intervals = [[1,3],[2,6],[8,10],[15,18]]
//输出：[[1,6],[8,10],[15,18]]
//解释：区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].
//
//
// 示例 2：
//
//
//输入：intervals = [[1,4],[4,5]]
//输出：[[1,5]]
//解释：区间 [1,4] 和 [4,5] 可被视为重叠区间。
//
//
//
// 提示：
//
//
// 1 <= intervals.length <= 104
// intervals[i].length == 2
// 0 <= starti <= endi <= 104
//
// Related Topics 数组 排序
// 👍 1118 👎 0


import java.util.ArrayList;
import java.util.List;

//leetcode submit region begin(Prohibit modification and deletion)
public class L56 {

    public static void main(String[] args) {
        System.out.println(merge(new int[][]{{1, 3}, {2, 6}, {8, 10}, {15, 18}}));
    }

    public static int[][] merge(int[][] intervals) {
        //计数排序
        int[][] nums = new int[1000][2];
        for (int i = 0; i < nums.length; i++) {
            nums[i] = null;
        }
        for (int i = 0; i < intervals.length; i++) {
            int[] n = nums[intervals[i][0]];
            if (n == null || intervals[i][1] > n[1]) {
                nums[intervals[i][0]] = intervals[i];
            }
        }
        List<int[]> res = new ArrayList<>();
        for (int[] num : nums) {
            if (num != null) {
                if (res.size() == 0) {
                    res.add(num);
                } else {
                    int[] last = res.get(res.size() - 1);
                    if (last[1] < num[0]) {
                        res.add(num);
                    } else {
                        if (num[1] > last[1]) {
                            res.remove(res.size() - 1);
                            int[] row = new int[2];
                            row[0] = last[0];
                            row[1] = num[1];
                            res.add(row);
                        }
                    }
                }
            }
        }
        return res.toArray(new int[][]{});
    }
}
//leetcode submit region end(Prohibit modification and deletion)
